#include "../tools.h"


class Solution {
public:
    unordered_map<int, pair<TreeNode*, bool>> fa_arr;
    void fill_fa(TreeNode* node, TreeNode* father){
        if(node == nullptr) return;
        fa_arr[node->val].first = father;
        fa_arr[node->val].second = false;

        if(node->left != nullptr) fill_fa(node->left, node);
        if(node->right != nullptr) fill_fa(node->right, node);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
        fill_fa(root, nullptr);

        while(p != nullptr){
            fa_arr[p->val].second = true;
            p = fa_arr[p->val].first;
        }

        while(q != nullptr){
            if(fa_arr[q->val].second == true) return q;
            q = fa_arr[q->val].first;
        }
        return nullptr;
    }
};

int main(int argc, char const *argv[])
{
    
    vector<int> root = {3,5,1,6,2,0,8,-1,-1,7,4};
    int p = 5, q = 1;

    TreeNode* tree = create_tree(root);
    show(tree);
    cout << endl;

    TreeNode* nodep = get_tree_node(tree, p);
    // show(nodep);
    // cout << endl;
    TreeNode* nodeq = get_tree_node(tree, q);
    // show(nodeq);

    Solution s;
    TreeNode* res = s.lowestCommonAncestor(tree, nodep, nodeq);
    cout << res->val << endl;




    return 0;
}
